package leetcode.others;

import java.util.Arrays;

//169. 多数元素
public class MajorityElement {
    public static void main(String[] args) {
        int[] a = {1, 5, 6, 8, 8, 8, 7, 6, 8, 8};
        System.out.println(majorityElement3(a));
    }

    public static int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    //摩尔投票
    public static int majorityElement2(int[] nums) {
        return 0;
    }

    //从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，
    // 减到0就重新换个数开始计数，总能找到最多的那个
    public static int majorityElement3(int[] nums) {
        int count = 1;
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (res == nums[i]) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    res = nums[i + 1];
                }
            }
        }
        return res;
    }
}
